package problems.daily.y2021m6;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * @author habitplus
 * @since 2021-06-26 09:26
 */
public class T20210626N1 {
    // 773. 滑动谜题
    // 在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。
    //      一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换。
    //      最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
    //      给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1。
    //
    //链接：https://leetcode-cn.com/problems/sliding-puzzle
    public int slidingPuzzle(int[][] board) {
        // bfs
        // 得到初始状态
        StringBuilder sb = new StringBuilder();
        for (int[] rows : board) {
            for (int e : rows) {
                sb.append(e);
            }
        }
        String initStatus = sb.toString();
        if ("123450".equals(initStatus)) {
            return 0;
        }

        Queue<String> que = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        int step = 0;
        que.offer(initStatus);
        visited.add(initStatus);

        // 存储迷宫 6 的位置的相邻位置编号 (0,1,2,3,4,5)
        int[][] neighbors = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};

        while (!que.isEmpty()) {
            ++step;
            for (int i = que.size(); i > 0; i--) {
                String curStatus = que.poll();

                // 找到 '0' 所在的位置下标
                int zeroIdx = curStatus.indexOf('0');
//                System.out.println(zeroIdx + " --> " + neighbors[zeroIdx].length);
                // 遍历 ‘0’ 的相邻位置，得到下一个状态
                for (int idx : neighbors[zeroIdx]) {
                    String nxtStatus = swap(curStatus, zeroIdx, idx);
                    if (!visited.contains(nxtStatus)) {
                        que.offer(nxtStatus);
                        visited.add(nxtStatus);
                    }
                }
                // 找到了目标状态
                if (visited.contains("123450")) {
                    return step;
                }
            }
        }
        return -1;
    }

    private String swap(String curStatus, int i, int j) {
        char[] chs = curStatus.toCharArray();
        char t = chs[i];
        chs[i] = chs[j];
        chs[j] = t;
        return new String(chs, 0, 6);
    }

    public static void main(String[] args) {
        System.out.println(new T20210626N1().slidingPuzzle(new int[][]{{1, 2, 3}, {5, 4, 0}}));
    }

}
